<?php
include 'Node.php';

$fileName = 'tree.txt';
echo 'Reading in file: ' . $fileName . '<br>';

$tree = createTree('tree.txt');
if ($tree != null) {
	echo 'Pre-order: '; preOrder($tree); echo '<br>';
	echo 'In-order: '; inOrder($tree); echo '<br>';
	echo 'Post-order: '; postOrder($tree); echo '<br>';
	echo 'Tree max height: ' . getMaxTreeHeight($tree) . '<br>';
	echo 'Tree max width: ' . getMaxTreeWidth($tree) . '<br><br>';
	echo 'Tree width at each level:<br>';
	$widths = array();
	getTreeWidthLevels($tree, 1, $widths);
	foreach ($widths as $level => $count) {
		echo 'Level ' . $level . ' - width: ' . $count . '<br>';
	}
	echo '<br>Parenthesised version of tree:<br>';
	getParenthesisedTree($tree);
} else {
	echo 'Empty tree!';
}

function getParenthesisedTree(Node $node = null) {
	
	if ($node == null) {
		return;
	}
	
	echo '(<b>' , $node->getLabel() . '</b>';
	getParenthesisedTree($node->getLeftChild());
	getParenthesisedTree($node->getRightChild());
	echo ')';
	
}

function createTree($fileName) {
	$file = fopen($fileName, 'r') or die('Can\'t open file!');
	$header = fgets($file); // fgets() gets a line from a file
	$header2 = fgets($file);
	
	$root = null;
	if ($firstLine = fgets($file)) {
		$root = new Node();
		list($label, $leftNodeLabel, $rightNodeLabel) = preg_split('/\s+/', $firstLine);

		$root->setLabel($label);
		
		if ($leftNodeLabel != Node::NIL) {
			$leftChild = new Node($leftNodeLabel);
			$root->setLeftChild($leftChild);
		}
		
		if ($rightNodeLabel != Node::NIL) {
			$rightChild = new Node($rightNodeLabel);
			$root->setRightChild($rightChild);
		}
	}

	while (!feof($file)) {
		list($label, $leftNodeLabel, $rightNodeLabel) = preg_split('/\s+/', fgets($file));
		
		$node = search($root, $label);
		
		// Is this needed? The node should've been created already as a child in previous steps.
		if ($node == null) {
			$node = new Node($label);
		}
		
		if ($leftNodeLabel != Node::NIL) {
			$leftChild = new Node($leftNodeLabel);
			$node->setLeftChild($leftChild);
		}
		
		if ($rightNodeLabel != Node::NIL) {
			$rightChild = new Node($rightNodeLabel);
			$node->setRightChild($rightChild);
		}
	}

	return $root;
}

function search(Node $node, $searchableLabel) {
	if ($node == null) {
		
		return null;
	}
	
	if ($node->getLabel() == $searchableLabel) {
		
		return $node;
	} else {
		if ($node->getLeftChild() != null) {
			$nodeFound = search($node->getLeftChild(), $searchableLabel);
			if ($nodeFound != null) {
				
				return $nodeFound;
			}
		}
		
		if ($node->getRightChild() != null) {
			$nodeFound = search($node->getRightChild(), $searchableLabel);
			if ($nodeFound != null) {
				
				return $nodeFound;
			}
		}
	}
}

function getMaxTreeHeight(Node $node = null) {
	if ($node == null) {
		
		return 0;
	}
	
	$leftTreeHeight = getMaxTreeHeight($node->getLeftChild());
	$rightTreeHeight = getMaxTreeHeight($node->getRightChild());
	
	if ($leftTreeHeight < $rightTreeHeight) {
		
		return $rightTreeHeight + 1;
	}
	
	return $leftTreeHeight + 1;
}

function getMaxTreeWidth(Node $node = null, $level = 2) {
	if ($node == null) {
		
		return 0;
	}
	
	$maxWidth = 1;
	$currentWidth = 1;
	$level = 2;
	
	while ($currentWidth > 0) {
		$currentWidth = getTreeWidth($node, $level++);
		$maxWidth = max(array($currentWidth, $maxWidth));
	}
	
	return $maxWidth;
}

function getTreeWidth(Node $node = null, $level = 1) {
	
	if ($node == null) {
		
		return 0;
	}
	
	if ($level == 1) {
		return 1;
	}
	
	return getTreeWidth($node->getLeftChild(), $level-1) + getTreeWidth($node->getRightChild(), $level-1);
}

function getTreeWidthLevels(Node $node = null, $level) {
	global $widths; // using global variable
	if ($node == null) {
		return;
	}
	
	if (isset($widths[$level])) {
		$widths[$level] += 1;
	} else {
		$widths[$level] = 1;
	}
	
	getTreeWidthLevels($node->getLeftChild(), $level+1, $widths);
	getTreeWidthLevels($node->getRightChild(), $level+1, $widths);
}

function preOrder(Node $node = null) {
	if ($node == null) {
		return;
	}
	
	echo $node->getLabel() . " ";
	preOrder($node->getLeftChild());
	preOrder($node->getRightChild());
}

function inOrder(Node $node = null) {
	if ($node == null) {
		return;
	}
	
	inOrder($node->getLeftChild());
	echo $node->getLabel() . " ";
	inOrder($node->getRightChild());
}

function postOrder(Node $node = null) {
	if ($node == null) {
		return;
	}
	
	postOrder($node->getLeftChild());
	postOrder($node->getRightChild());
	echo $node->getLabel() . " ";
}

